{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Linked List Components"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #linked-list"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numComponents"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #链表组件"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定链表头结点&nbsp;<code>head</code>，该链表上的每个结点都有一个 <strong>唯一的整型值</strong> 。同时给定列表&nbsp;<code>nums</code>，该列表是上述链表中整型值的一个子集。</p>\n",
    "\n",
    "<p>返回列表&nbsp;<code>nums</code>&nbsp;中组件的个数，这里对组件的定义为：链表中一段最长连续结点的值（该值必须在列表&nbsp;<code>nums</code>&nbsp;中）构成的集合。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例&nbsp;1：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/07/22/lc-linkedlistcom1.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> head = [0,1,2,3], nums = [0,1,3]\n",
    "<strong>输出:</strong> 2\n",
    "<strong>解释:</strong> 链表中,0 和 1 是相连接的，且 nums 中不包含 2，所以 [0, 1] 是 nums 的一个组件，同理 [3] 也是一个组件，故返回 2。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><strong>&nbsp;</strong><img src=\"https://assets.leetcode.com/uploads/2021/07/22/lc-linkedlistcom2.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> head = [0,1,2,3,4], nums = [0,3,1,4]\n",
    "<strong>输出:</strong> 2\n",
    "<strong>解释:</strong> 链表中，0 和 1 是相连接的，3 和 4 是相连接的，所以 [0, 1] 和 [3, 4] 是两个组件，故返回 2。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>链表中节点数为<code>n</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>0 &lt;= Node.val &lt; n</code></li>\n",
    "\t<li><code>Node.val</code>&nbsp;中所有值 <strong>不同</strong></li>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= n</code></li>\n",
    "\t<li><code>0 &lt;= nums[i] &lt; n</code></li>\n",
    "\t<li><code>nums</code> 中所有值 <strong>不同</strong></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [linked-list-components](https://leetcode.cn/problems/linked-list-components/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [linked-list-components](https://leetcode.cn/problems/linked-list-components/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[0,1,2,3]\\n[0,1,3]', '[0,1,2,3,4]\\n[0,3,1,4]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:\n",
    "\n",
    "        cur = head\n",
    "        res = 0\n",
    "\n",
    "        flag = False\n",
    "        while True:\n",
    "            if cur.val in nums:\n",
    "                flag = True\n",
    "            else:\n",
    "                if flag:\n",
    "                    res += 1\n",
    "                flag = False\n",
    "            cur = cur.next\n",
    "            if not cur:\n",
    "                if flag:\n",
    "                    res += 1\n",
    "                break\n",
    "            \n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "        return max_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:\n",
    "        if not head:return 0\n",
    "        ans = 0\n",
    "        cur = head\n",
    "        while cur:\n",
    "            if not cur.next:\n",
    "                if cur.val in nums:return ans+1\n",
    "                else:return ans\n",
    "            if cur.val in nums and cur.next.val not in nums:\n",
    "                ans += 1\n",
    "\n",
    "            cur = cur.next\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:\n",
    "        ans=0\n",
    "        while head:\n",
    "            cnt=0\n",
    "            while head and head.val in nums:\n",
    "                cnt+=1\n",
    "                head=head.next\n",
    "            ans+=cnt!=0\n",
    "            if head:\n",
    "                head=head.next\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:\n",
    "        cnt=0\n",
    "        sumcnt=0\n",
    "        while head:\n",
    "            if head.val in nums:\n",
    "                cnt+=1\n",
    "                head=head.next\n",
    "            else:\n",
    "                cnt=0\n",
    "                head=head.next\n",
    "            if cnt==1:\n",
    "                sumcnt+=1\n",
    "        return sumcnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:\n",
    "        out=0\n",
    "        compont=0\n",
    "        while head:\n",
    "            while head and head.val in nums:\n",
    "                compont=1\n",
    "                head=head.next\n",
    "            out+=compont\n",
    "            head=head.next if head else None\n",
    "            compont=0\n",
    "        return out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:\n",
    "        node_num_lst = []\n",
    "        current = head\n",
    "        while current.next is not None:\n",
    "            node_num_lst.append(current.val)\n",
    "            current = current.next\n",
    "        node_num_lst.append(current.val)\n",
    "        component_lst = []\n",
    "        count = 0\n",
    "        for num in node_num_lst:\n",
    "            if num in nums:\n",
    "                component_lst.append(num)\n",
    "            else:\n",
    "                if component_lst:\n",
    "                    count += 1\n",
    "                    component_lst.clear()\n",
    "        if component_lst:\n",
    "            count += 1\n",
    "            component_lst.clear()\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:\n",
    "\n",
    "        cur = head\n",
    "        res = 0\n",
    "\n",
    "        flag = False\n",
    "        while True:\n",
    "            if cur.val in nums:\n",
    "                flag = True\n",
    "            else:\n",
    "                if flag:\n",
    "                    res += 1\n",
    "                flag = False\n",
    "            cur = cur.next\n",
    "            if not cur:\n",
    "                if flag:\n",
    "                    res += 1\n",
    "                break\n",
    "            \n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "        return max_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:\n",
    "        count = 0\n",
    "\n",
    "        while head:\n",
    "            if head.val in nums and (not head.next or head.next.val not in nums):\n",
    "                count += 1\n",
    "            head = head.next\n",
    "\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:\n",
    "        cnt=0\n",
    "        sumcnt=0\n",
    "        p=head\n",
    "        while p:\n",
    "            if p.val in nums:\n",
    "                cnt+=1\n",
    "            else:\n",
    "                cnt=0\n",
    "            if cnt==1:\n",
    "                sumcnt+=1\n",
    "            p=p.next\n",
    "        return sumcnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:\n",
    "        cnt=0\n",
    "        sumcnt=0\n",
    "        while head:\n",
    "            if head.val in nums:\n",
    "                cnt+=1\n",
    "            else:\n",
    "                cnt=0\n",
    "            if cnt==1:\n",
    "                sumcnt+=1\n",
    "            head=head.next\n",
    "        return sumcnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:\n",
    "        count = 0\n",
    "        inc = False\n",
    "        while head:\n",
    "            if head.val in nums:\n",
    "                if not inc:\n",
    "                    count += 1\n",
    "                    inc = True\n",
    "            else:\n",
    "                inc = False\n",
    "            head = head.next\n",
    "        \n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:\n",
    "        cnt=0\n",
    "        sumcnt=0\n",
    "        while head:\n",
    "            if head.val in nums:\n",
    "                cnt+=1\n",
    "                head=head.next\n",
    "            else:\n",
    "                cnt=0\n",
    "                head=head.next\n",
    "            if cnt==1:\n",
    "                sumcnt+=1\n",
    "        return sumcnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:\n",
    "        ct=0\n",
    "        flag=False\n",
    "\n",
    "        while head:\n",
    "            if head.val in nums:\n",
    "                if not flag:\n",
    "                    ct+=1\n",
    "                    flag=True\n",
    "            else:\n",
    "                flag=False\n",
    "            head=head.next\n",
    "        return ct\n",
    "                \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:\n",
    "\n",
    "        # max_len = 0\n",
    "        # cur_len = 0\n",
    "        # ans = 0\n",
    "        # while head:\n",
    "        #     if head.val in nums:\n",
    "        #         cur_len+=1\n",
    "        #         if cur_len>max_len:\n",
    "        #             max_len=cur_len\n",
    "        #             ans=1\n",
    "        #         elif cur_len==max_len:\n",
    "        #             ans+=1\n",
    "        #     else:\n",
    "        #         cur_len=0\n",
    "        #     head = head.next\n",
    "        # return ans\n",
    "\n",
    "        \n",
    "        inset=False\n",
    "        ans = 0\n",
    "        while head:\n",
    "            if head.val in nums:\n",
    "                if not inset:\n",
    "                    inset=True\n",
    "                    ans+=1\n",
    "\n",
    "            else:\n",
    "                inset=False\n",
    "\n",
    "            head = head.next\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:\n",
    "\n",
    "        num_dict = {num: True for num in nums}\n",
    "        cur = head\n",
    "        res = 0\n",
    "\n",
    "        flag = False\n",
    "        while True:\n",
    "            if num_dict.get(cur.val, False):\n",
    "                flag = True\n",
    "            else:\n",
    "                if flag:\n",
    "                    res += 1\n",
    "                flag = False\n",
    "            cur = cur.next\n",
    "            if not cur:\n",
    "                if flag:\n",
    "                    res += 1\n",
    "                break\n",
    "            \n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "        return max_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:\n",
    "        p=head\n",
    "        cnt=0\n",
    "        isStart=False\n",
    "        dic=dict()\n",
    "        for num in nums:\n",
    "            dic[num]=1\n",
    "        while p:\n",
    "            if p.val in dic:\n",
    "                isStart=True\n",
    "            else:\n",
    "                if isStart:\n",
    "                    isStart=False\n",
    "                    cnt+=1\n",
    "            p=p.next\n",
    "        if isStart:\n",
    "            cnt+=1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:\n",
    "        p=head\n",
    "        cnt=0\n",
    "        isStart=False\n",
    "        dic=dict()\n",
    "        for num in nums:\n",
    "            dic[num]=1\n",
    "        while p:\n",
    "            if p.val in dic:\n",
    "                isStart=True\n",
    "            else:\n",
    "                if isStart:\n",
    "                    isStart=False\n",
    "                    cnt+=1\n",
    "            p=p.next\n",
    "        if isStart:\n",
    "            cnt+=1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... \n",
    "        \n",
    "        nums = set(nums)\n",
    "        count = 0\n",
    "        while head:\n",
    "            if head.val not in nums:\n",
    "                head = head.next\n",
    "            else:\n",
    "                count += 1\n",
    "                while head and head.val in nums:\n",
    "                    head = head.next\n",
    "        return count\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:\n",
    "        nums_set = set(nums)\n",
    "        answer = 0 \n",
    "        while head:\n",
    "            if head.val in nums_set:\n",
    "                answer += 1 \n",
    "                head = head.next \n",
    "                while head and (head.val in nums_set):\n",
    "                    head = head.next \n",
    "            else:\n",
    "                head = head.next \n",
    "        return answer "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:\n",
    "        st = set(nums)\n",
    "        p = head\n",
    "        ans = 0\n",
    "        while p:\n",
    "            if p.val in st:\n",
    "                ans += 1\n",
    "                while p and p.val in st:\n",
    "                    p = p.next\n",
    "            else:\n",
    "                p = p.next\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        nset = set(nums)\n",
    "        while head:\n",
    "            if head.val in nset:\n",
    "                while head and head.val in nset:\n",
    "                    head = head.next\n",
    "                ans += 1\n",
    "            else:\n",
    "                head = head.next\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:\n",
    "        s = set(nums)\n",
    "        ans = 0\n",
    "        while head:\n",
    "            while head and head.val not in s:\n",
    "                head = head.next\n",
    "            if head:ans += 1\n",
    "            while head and head.val in s:\n",
    "                head = head.next\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:\n",
    "        numSet = set(nums)\n",
    "        inSet = False\n",
    "        res = 0\n",
    "        while head:\n",
    "            if head.val not in numSet:\n",
    "                inSet = False\n",
    "            elif  head.val in numSet and not inSet:\n",
    "                inSet = True\n",
    "                res+=1\n",
    "            head = head.next\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:\n",
    "\n",
    "        num_dict = {num: True for num in nums}\n",
    "        cur = head\n",
    "        res = 0\n",
    "\n",
    "        flag = False\n",
    "        while True:\n",
    "            if num_dict.get(cur.val, False):\n",
    "                flag = True\n",
    "            else:\n",
    "                if flag:\n",
    "                    res += 1\n",
    "                flag = False\n",
    "            cur = cur.next\n",
    "            if not cur:\n",
    "                if flag:\n",
    "                    res += 1\n",
    "                break\n",
    "            \n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "        return max_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:\n",
    "        numsSet = set(nums)\n",
    "        res = 0\n",
    "        inSet = False\n",
    "        while head:\n",
    "            if head.val not in nums:\n",
    "                inSet = False\n",
    "            elif not inSet:\n",
    "                inSet = True\n",
    "                res += 1\n",
    "            head = head.next\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:\n",
    "        hash_set = set(nums)\n",
    "        count = 0\n",
    "        falg = False\n",
    "        while head:\n",
    "            if head.val in hash_set:\n",
    "                if not falg:\n",
    "                    count += 1\n",
    "                falg = True\n",
    "            else:\n",
    "                falg = False\n",
    "            head = head.next\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:\n",
    "\n",
    "        num_dict = {num: True for num in nums}\n",
    "        cur = head\n",
    "        res = 0\n",
    "\n",
    "        flag = False\n",
    "        while True:\n",
    "            if num_dict.get(cur.val, False):\n",
    "                flag = True\n",
    "            else:\n",
    "                if flag:\n",
    "                    res += 1\n",
    "                flag = False\n",
    "            cur = cur.next\n",
    "            if not cur:\n",
    "                if flag:\n",
    "                    res += 1\n",
    "                break\n",
    "            \n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "        return max_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:\n",
    "        s = set()\n",
    "        for v in nums:\n",
    "            s.add(v)\n",
    "\n",
    "        flag, cnt = False, 0\n",
    "        while head:\n",
    "            if head.val in s:\n",
    "                flag = True\n",
    "            else:\n",
    "                if flag:\n",
    "                    flag = False\n",
    "                    cnt += 1\n",
    "            head = head.next\n",
    "        cnt += int(flag)\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:\n",
    "        nums = set(nums)\n",
    "\n",
    "        ret = 0\n",
    "        cur = 0\n",
    "\n",
    "        while head:\n",
    "            if head.val in nums:\n",
    "                cur += 1\n",
    "            else:\n",
    "                if cur != 0:\n",
    "                    ret += 1\n",
    "                    cur = 0\n",
    "            head = head.next\n",
    "        ret += 1 if cur > 0 else 0\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:\n",
    "        p=head\n",
    "        cnt=0\n",
    "        isStart=False\n",
    "        s=set()\n",
    "        for num in nums:\n",
    "            s.add(num)\n",
    "        while p:\n",
    "            if p.val in s:\n",
    "                isStart=True\n",
    "            else:\n",
    "                if isStart:\n",
    "                    isStart=False\n",
    "                    cnt+=1\n",
    "            p=p.next\n",
    "        if isStart:\n",
    "            cnt+=1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:\n",
    "        nums = set(nums)\n",
    "        ans = 0\n",
    "        # ret = 0\n",
    "        p = head\n",
    "        start,end = False,False\n",
    "        while p:\n",
    "            while p:                \n",
    "                if p.val not in nums:\n",
    "                    p = p.next\n",
    "                else:\n",
    "                    start = True\n",
    "                    break\n",
    "            else:\n",
    "                break\n",
    "            while p:\n",
    "                end = True\n",
    "                if p.val in nums:\n",
    "                    p = p.next\n",
    "                else:\n",
    "                    break\n",
    "                    \n",
    "            if start and end:              \n",
    "                ans += 1\n",
    "            start = end = False\n",
    "            # p = p.next\n",
    "            # ans = max(ans,ret)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        nset = set(nums)\n",
    "        while head:\n",
    "            if head.val in nset:\n",
    "                while head and head.val in nset:\n",
    "                    head = head.next\n",
    "                ans += 1\n",
    "            else:\n",
    "                head = head.next\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:\n",
    "        nums = set(nums)\n",
    "        result = 0\n",
    "        count = 0\n",
    "        current = head\n",
    "        while current:\n",
    "            if current.val in nums:\n",
    "                count += 1\n",
    "            else:\n",
    "                if count != 0:\n",
    "                    result += 1\n",
    "                    count = 0\n",
    "\n",
    "            current = current.next\n",
    "\n",
    "        if count != 0:\n",
    "            result += 1\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:\n",
    "        # nums = set(nums)\n",
    "        # res = count = flag = 0\n",
    "        # p = head \n",
    "        # while p and count < len(nums):\n",
    "        #     if p.val in nums:\n",
    "        #         count += 1\n",
    "        #         if not flag:\n",
    "        #             res += 1\n",
    "        #             flag = 1\n",
    "        #     else:\n",
    "        #         flag = 0\n",
    "        #     p = p.next\n",
    "        # return res\n",
    "\n",
    "        # -------------------\n",
    "        # res = 0\n",
    "        # s = set(nums)\n",
    "        # while head:\n",
    "        #     while head and head.val not in s:\n",
    "        #         head = head.next\n",
    "        #     res += head is not None \n",
    "        #     while head and head.val in s:\n",
    "        #         head = head.next\n",
    "        # return res \n",
    "\n",
    "        # -------------------\n",
    "        res = 0\n",
    "        s = set(nums)\n",
    "        flag = 0\n",
    "        while head:\n",
    "            if head.val not in s:\n",
    "                flag = 0\n",
    "            elif not flag:\n",
    "                flag = 1\n",
    "                res += 1\n",
    "            head = head.next\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:\n",
    "        nums = set(nums)\n",
    "        ans = 0\n",
    "        curr = 0\n",
    "        while head:\n",
    "            if head.val in nums:\n",
    "                curr = 1\n",
    "            else:\n",
    "                if curr != 0:\n",
    "                    ans += 1\n",
    "                curr = 0\n",
    "            head = head.next\n",
    "        if curr != 0:\n",
    "            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:\n",
    "        nums_set = set(nums)\n",
    "        cur = head\n",
    "        curlen = 0\n",
    "        result = 0\n",
    "        while(cur):\n",
    "            if(cur.val in nums_set):\n",
    "                curlen += 1\n",
    "            else:\n",
    "                if(curlen > 0):\n",
    "                    result += 1\n",
    "                curlen = 0\n",
    "            cur = cur.next \n",
    "        if(curlen > 0):\n",
    "            result += 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        hashset = set(nums)\n",
    "        cur = head\n",
    "        pre = ListNode(-1)\n",
    "        pre.next = head\n",
    "\n",
    "        while cur:\n",
    "            if pre.val in hashset and cur.val not in hashset:\n",
    "                res += 1\n",
    "            if not cur.next:\n",
    "                if cur.val in hashset:\n",
    "                    res += 1\n",
    "            cur = cur.next\n",
    "            pre = pre.next\n",
    "            \n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:\n",
    "        if not head:\n",
    "            return None\n",
    "        \n",
    "        ans = 0\n",
    "        recode = set(nums)\n",
    "        while head:\n",
    "            while head and head.val not in recode:\n",
    "                head = head.next\n",
    "            ans += head is not None\n",
    "            while head and head.val in recode:\n",
    "                head = head.next\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:\n",
    "       # 在链表原地解决\n",
    "        ans = 0\n",
    "        numSet = set(nums)\n",
    "        while head:\n",
    "            if head.val in numSet:\n",
    "                while head and head.val in numSet:\n",
    "                    head = head.next\n",
    "                ans +=1\n",
    "            else:\n",
    "                head = head.next\n",
    "        return ans\n",
    "\n",
    "        # 转化为数组求解\n",
    "        num = []\n",
    "        while head:\n",
    "            num.append(head.val)\n",
    "            head = head.next\n",
    "        num.append(float('inf'))\n",
    "        n = len(num)\n",
    "        index = 0\n",
    "        res = 0\n",
    "        numSet = set(nums)\n",
    "        while index<n:\n",
    "            if num[index] in numSet:\n",
    "                while num[index] in numSet and index<n:\n",
    "                    index+=1\n",
    "                res+=1\n",
    "            else:\n",
    "                index+=1\n",
    "\n",
    "        return res\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        s = set(nums)\n",
    "        while head:\n",
    "            while head and head.val not in s:\n",
    "                head = head.next\n",
    "            if head:ans += 1\n",
    "            while head and head.val in s:\n",
    "                head = head.next\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:\n",
    "        nums = set(nums)\n",
    "        p = head\n",
    "        comp = 0\n",
    "        while p:\n",
    "            flag = False\n",
    "            while p and p.val not in nums:\n",
    "                p = p.next\n",
    "            while p and p.val in nums:\n",
    "                p = p.next\n",
    "                flag = True\n",
    "            if flag:\n",
    "                comp += 1\n",
    "        return comp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:\n",
    "        s = set(nums)\n",
    "        ans = 0\n",
    "        while head:\n",
    "            while head and head.val not in s:\n",
    "                head = head.next\n",
    "            if head:ans += 1\n",
    "            while head and head.val in s:\n",
    "                head = head.next\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:\n",
    "        nums_set = set(nums)\n",
    "        cur = head\n",
    "        curlen = 0\n",
    "        result = 0\n",
    "        while(cur):\n",
    "            if(cur.val in nums_set):\n",
    "                curlen += 1\n",
    "            else:\n",
    "                if(curlen > 0):\n",
    "                    result += 1\n",
    "                curlen = 0\n",
    "            cur = cur.next \n",
    "        if(curlen > 0):\n",
    "            result += 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        s = set(nums)\n",
    "        while head:\n",
    "            while head and head.val not in s:\n",
    "                head = head.next\n",
    "            if head:ans += 1\n",
    "            while head and head.val in s:\n",
    "                head = head.next\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:\n",
    "        nums = set(nums)\n",
    "        count = 0\n",
    "        inc = False\n",
    "        while head:\n",
    "            if head.val in nums:\n",
    "                if not inc:\n",
    "                    count += 1\n",
    "                    inc = True\n",
    "            else:\n",
    "                inc = False\n",
    "            head = head.next\n",
    "        \n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:\n",
    "        \n",
    "        res=0\n",
    "        temp=set(nums)\n",
    "        while head:\n",
    "            while head  and head.val not in temp:\n",
    "                head=head.next\n",
    "            if head:\n",
    "                res+=1\n",
    "            #res+=head is not None\n",
    "            while head and head .val in temp:\n",
    "                head=head.next\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:\n",
    "        s = set(nums)\n",
    "        ans = 0\n",
    "        while head:\n",
    "            if head.val in s:\n",
    "                while head and head.val in s:\n",
    "                    head = head.next\n",
    "                ans += 1\n",
    "            else:\n",
    "                head = head.next\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        prev = False\n",
    "        s = set(nums)\n",
    "        while head:\n",
    "            if head.val in s and not prev:\n",
    "                res += 1\n",
    "                prev = True\n",
    "            if head.val not in s:\n",
    "                prev = False\n",
    "            head = head.next\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:\n",
    "        set_nums = set(nums)\n",
    "        ans = 0\n",
    "        cnt = 0\n",
    "        while head:\n",
    "            num = head.val\n",
    "            if num in set_nums:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                ans += (1 if cnt else 0)\n",
    "                cnt = 0\n",
    "            head = head.next\n",
    "        ans += (1 if cnt else 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:\n",
    "        if not head:\n",
    "            return None\n",
    "        \n",
    "        ans = 0\n",
    "        recode = set(nums)\n",
    "        while head:\n",
    "            while head and head.val not in recode:\n",
    "                head = head.next\n",
    "            if head is not None:\n",
    "                ans += 1\n",
    "            while head and head.val in recode:\n",
    "                head = head.next\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:\n",
    "        # nums = set(nums)\n",
    "        # res = count = flag = 0\n",
    "        # p = head \n",
    "        # while p and count < len(nums):\n",
    "        #     if p.val in nums:\n",
    "        #         count += 1\n",
    "        #         if not flag:\n",
    "        #             res += 1\n",
    "        #             flag = 1\n",
    "        #     else:\n",
    "        #         flag = 0\n",
    "        #     p = p.next\n",
    "        # return res\n",
    "\n",
    "        # -------------------\n",
    "        res = 0\n",
    "        s = set(nums)\n",
    "        while head:\n",
    "            while head and head.val not in s:\n",
    "                head = head.next\n",
    "            res += head is not None \n",
    "            while head and head.val in s:\n",
    "                head = head.next\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:\n",
    "        nums_set = set(nums)\n",
    "        answer = 0 \n",
    "        while head:\n",
    "            if head.val in nums_set:\n",
    "                answer += 1 \n",
    "                head = head.next \n",
    "                while head and (head.val in nums_set):\n",
    "                    head = head.next \n",
    "            else:\n",
    "                head = head.next \n",
    "        return answer "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "class ListNode:\n",
    "    def __init__(self, val=0, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\n",
    "\n",
    "from typing import List, Optional\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        nums = set(nums)\n",
    "        ans = 0\n",
    "        p = head\n",
    "        f = False\n",
    "        while p:\n",
    "            if p.val in nums:\n",
    "                if not f:\n",
    "                    ans += 1\n",
    "                    f = True\n",
    "            else:\n",
    "                f = False\n",
    "            p = p.next\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\r\n",
    "# class ListNode:\r\n",
    "#     def __init__(self, val=0, next=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.next = next\r\n",
    "class Solution:\r\n",
    "    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:\r\n",
    "        nums_set=set(nums)\r\n",
    "        ret=0\r\n",
    "        inset=False\r\n",
    "        while head:\r\n",
    "            if head.val in nums_set:\r\n",
    "                if not inset:\r\n",
    "                    inset=True\r\n",
    "                    ret+=1\r\n",
    "            else:\r\n",
    "                inset=False\r\n",
    "            head=head.next\r\n",
    "        return ret\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:\n",
    "        s = set(nums)\n",
    "        ans = 0\n",
    "        while head:\n",
    "            while head and head.val not in s:\n",
    "                head = head.next\n",
    "            if head:ans += 1\n",
    "            while head and head.val in s:\n",
    "                head = head.next\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:\n",
    "        nums = set(nums)\n",
    "        p = head\n",
    "        cnt = 0\n",
    "        flag =False\n",
    "        while p:\n",
    "            if p.val in nums:\n",
    "                flag = True\n",
    "                nums.remove(p.val)\n",
    "            elif flag and p.val not in nums:\n",
    "                cnt+=1\n",
    "                flag=False\n",
    "            p = p.next\n",
    "        if flag:\n",
    "            cnt+=1\n",
    "        return cnt\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "[0,1,2,3]\n",
    "[0,1,3]\n",
    "[0,1,2,3,4]\n",
    "[0,3,1,4]\n",
    "\n",
    "The number of nodes in the linked list is n.\n",
    "1 <= n <= 1e4\n",
    "0 <= Node.val < n\n",
    "All the values Node.val are unique.\n",
    "1 <= nums.length <= n\n",
    "0 <= nums[i] < n\n",
    "All the values of nums are unique.\n",
    "\n",
    "Array, Hash Table, Linked List\n",
    "\"\"\"\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:\n",
    "        numsSet = set(nums)\n",
    "        res = 0\n",
    "        while head:\n",
    "            if head.val in numsSet and \\\n",
    "                    (not head.next or not head.next.val in numsSet):\n",
    "                res += 1\n",
    "            head = head.next\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:\n",
    "        numsSet = set(nums)\n",
    "        inSet = False\n",
    "        res = 0\n",
    "        while head:\n",
    "            if head.val not in numsSet:\n",
    "                inSet = False\n",
    "            elif not inSet:\n",
    "                inSet = True\n",
    "                res += 1\n",
    "            head = head.next\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:\n",
    "        s = set(nums)\n",
    "        ret = 0\n",
    "        p = head\n",
    "        while p != None:\n",
    "            if p.val in s and (p.next == None or p.next.val not in s):\n",
    "                ret += 1 \n",
    "            p = p.next\n",
    "\n",
    "        return ret\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:\n",
    "        nset = set(nums)\n",
    "        res = 0\n",
    "        while head != None:\n",
    "            if head.val in nset:\n",
    "                res += 1\n",
    "                while head != None and head.val in nset:\n",
    "                    head = head.next\n",
    "            else:\n",
    "                head = head.next\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class DisjointSet:\n",
    "  def __init__(self, n):\n",
    "    self.parent = [i for i in range(n)]\n",
    "    self.rank = [0] * n\n",
    "\n",
    "  def get_parent(self):\n",
    "    return self.parent\n",
    "\n",
    "  def find(self, x):\n",
    "    if self.parent[x] == x:\n",
    "      return x\n",
    "\n",
    "    self.parent[x] = self.find(self.parent[x])\n",
    "    return self.parent[x]\n",
    "\n",
    "  def union(self, x, y):\n",
    "    px = self.parent[x]\n",
    "    py = self.parent[y]\n",
    "\n",
    "    if self.rank[px] < self.rank[py]:\n",
    "      self.parent[px] = py\n",
    "      self.rank[py] += 1\n",
    "    else:\n",
    "      self.parent[py] = px\n",
    "      self.rank[px] += 1\n",
    "\n",
    "class Solution:\n",
    "    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:\n",
    "        n, pos = 0, head\n",
    "        while pos:\n",
    "            n += 1\n",
    "            pos = pos.next\n",
    "\n",
    "        ds = DisjointSet(n)\n",
    "        nums_set = set(nums)\n",
    "        pos = head\n",
    "        while pos and pos.next:\n",
    "            if pos.val in nums_set and pos.next.val in nums_set:\n",
    "                ds.union(pos.val, pos.next.val)\n",
    "            pos = pos.next\n",
    "\n",
    "        return len(set(ds.parent).intersection(nums_set))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\r\n",
    "# class ListNode:\r\n",
    "#     def __init__(self, val=0, next=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.next = next\r\n",
    "class Solution:\r\n",
    "    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:\r\n",
    "        maps={}\r\n",
    "        pre,cur=None,head\r\n",
    "        while cur:\r\n",
    "            nxt=cur.next.val if cur.next else None\r\n",
    "            maps[cur.val]=[pre,nxt]\r\n",
    "            pre=cur.val\r\n",
    "            cur=cur.next\r\n",
    "        \r\n",
    "        p=list(range(len(nums)))\r\n",
    "        # id_map={}\r\n",
    "        # idx=0\r\n",
    "        def find(x):\r\n",
    "            if x!=p[x]:\r\n",
    "                p[x]=find(p[x])\r\n",
    "            return p[x]\r\n",
    "        def connect(x,y):\r\n",
    "            px,py=find(x),find(y)\r\n",
    "            if px==py:\r\n",
    "                return\r\n",
    "            p[px]=p[py]\r\n",
    "        val2idx={n:i for i,n in enumerate(nums)}\r\n",
    "        visited=set()\r\n",
    "        for i,n in enumerate(nums):\r\n",
    "            pre,nxt=maps[n]\r\n",
    "            if pre in visited:\r\n",
    "                connect(i,val2idx[pre])\r\n",
    "            if nxt in visited:\r\n",
    "                connect(i,val2idx[nxt])\r\n",
    "            visited.add(n)\r\n",
    "        \r\n",
    "        ret=sum([p[i]==i for i in range(len(nums))])\r\n",
    "        return ret"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
